Quenched Averages for Self-Avoiding Walks and Polygons on Deterministic Fractals

We study rooted self avoiding polygons and self avoiding walks on deterministic fractal lattices of finite ramification index. Different sites on such lattices are not equivalent, and the number of rooted open walks W _n (S), and rooted self-avoiding polygons P _n (S) of n steps depend on the root S. We use exact recursion equations on the fractal to determine the generating functions for P _n (S), and W _n(S) for an arbitrary point S on the lattice. These are used to compute the averages ,, and over different positions of S. We find that the connectivity constant μ, and the radius of gyration exponent are the same for the annealed and quenched averages. However, , and , where the exponents and , take values different from the annealed case. These are expressed as the Lyapunov exponents of random product of finite-dimensional matrices. For the 3-simplex lattice, our numerical estimation gives and , to be compared with the known annealed values and .     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The Renormalization Group and Optimization of Entropy

We illustrate the possible connection that exists between the extremal properties of entropy expressions and the renormalization group (RG) approach when applied to systems with scaling symmetry. We consider three examples: (1) Gaussian fixed-point criticality in a fluid or in the capillary-wave model of an interface; (2) Lévy-like random walks with self-similar cluster formation; and (3) long-ranged bond percolation. In all cases we find a decreasing entropy function that becomes minimum under an appropriate constraint at the fixed point. We use an equivalence between random-walk distributions and order-parameter pair correlations in a simple fluid or magnet to study how the dimensional anomaly at criticality relates to walks with long-tailed distributions.     

Dynamic exponent in extremal models of pinning

The depinning transition of a front moving in a time-independent random potential is studied. The temporal development of the overall roughness w(L,t) of an initially flat front, , is the classical means to have access to the dynamic exponent. However, in the case of front propagation in quenched disorder via extremal dynamics, we show that the initial increase in front roughness implies an extra dependence over the system size which comes from the fact that the activity is essentially localized in a narrow region of space. We propose an analytic expression for the exponent and confirm this for different models (crack front propagation, Edwards-Wilkinson model in a quenched noise etc.). Received 27 August 1999     

Stability and other limit laws for exit times of random walks from a strip or a halfplane

We show that the passage time, T^*(r), of a random walk S_n above a horizontal boundary at r (r≥0) is stable (in probability) in the sense that as r→∞ for a deterministic function C(r)>0, if and only if the random walk is relatively stable in the sense that as n→∞ for a deterministic sequence B_n>0. The stability of a passage time is an important ingredient in some proofs in sequential analysis, where it arises during applications of Anscombe's Theorem. We also prove a counterpart for the almost sure stability of T^*(r), which we show is equivalent to E|X|<∞, EX>0. Similarly, counterparts for the exit of the random walk from the strip {|y|≤r} are proved. The conditions arefurther related to the relative stability of the maximal sum and the maximum modulus of the sums. Another result shows that the exit position of the random walk outside the boundaries at ±r drifts to ∞ as r→∞ if and only if the random walk drifts to ∞.     

Persistent Random Walks in Stationary Environment

We study the behavior of persistent random walks (RW) on the integers in a random environment. A complete characterization of the almost sure limit behavior of these processes, including the law of large numbers, is obtained. This is done in a general situation where the environmental sequence of random variables is stationary and ergodic. Szász and Tóth obtained a central limit theorem when the ratio /, of right- and left-transpassing probabilities satisfies /a<1 a.s. (for a given constant a). We consider the case where / has wider fluctuations; we shall observe that an unusual situation arises: the RW may converge a.s. to infinity even with zero drift. Then, we obtain nonclassical limiting distributions for the RW. Proofs are based on the introduction of suitable branching processes in order to count the steps performed by the RW.     

Numerical Simulations of Random Walk in Random Environment

This paper is concerned with the numerical simulation of a random walk in a random environment in dimension d = 2. Consider a nearest neighbor random walk on the 2-dimensional integer lattice. The transition probabilities at each site are assumed to be themselves random variables, but fixed for all time. This is the random environment. Consider a parallel strip of radius R centered on an axis through the origin. Let X _R be the probability that the walk that started at the origin exits the strip through one of the boundary lines. Then X _R is a random variable, depending on the environment. In dimension d = 1, the variable X _R converges in distribution to the Bernoulli variable, X = 0, 1 with equal probability, as R . Here the 2-dimensional problem is studied using Gauss-Seidel and multigrid algorithms.     

Different self-avoiding walks on percolation clusters: A small-cell real-space renormalization-group study

We calculate the average number of stepsN for edge-to-edge, normal, and indefinitely growing self-avoiding walks (SAWs) on two-dimensional critical percolation clusters, using the real-space renormalization-group approach, with small H cells. Our results are of the formN=AL ^D _SAW+B, whereL is the end-to-end distance. Similarly to several deterministic fractals, the fractal dimensionsD _SAW for these three different kinds of SAWs are found to be equal, and the differences between them appear in the amplitudesA and in the correction termsB. This behavior is atributed to the hierarchical nature of the critical percolation cluster.     

Random Walks on Trees and an Inequality of Means

We define trees generated by bi-infinite sequences, calculate their walk-invariant distribution and the speed of a biased random walk. We compare a simple random walk on a tree generated by a bi-infinite sequence with a simple random walk on an augmented Galton-Watson tree. We find that comparable simple random walks require the augmented Galton-Watson tree to be larger than the corresponding tree generated by a bi-infinite sequence. This is due to an inequality for random variables with values in [1, [ involving harmonic, geometric and arithmetic mean.     

Trapping of random walks on the line

Several features of the trapping of random walks on a one-dimensional lattice are analyzed. The results of this investigation are as follows: (1) The correction term to the known asymptotic form for the survival probability ton steps is O(( ₂n)^–1/3), where =–ln(1–c), andc is the trap concentration. (2) The short time form for the survival probability is found to be exp[–a(c)n ^1/2], wherea(c) is given in Eq. (21). (3) The mean-square displacement of a surviving random walker is found to go liken ^2/3for largen. (4) When the distribution of trap-free regions is changed so that very large regions are much rarer than for ideally random trap placement the asymptotic survival probability changes its dependence onn. One such model is studied.